package interview.huawei.tjt.training.dongtaiguihua;

/**
 * 0-1背包问题，使用一维数组实现
 */
public class BagOf01_2 {

    public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagSize = 4;
        testWeightBagProblem(weight, value, bagSize);
    }

    private static void testWeightBagProblem(int[] weight, int[] value, int bagSize) {

        int[] dp = new int[bagSize + 1];
        // 遍历顺序：先遍历物品，再遍历背包容量
        // 倒叙遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！
        //一维dp的写法，背包容量一定是要倒序遍历，如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。
        for (int i = 0; i < weight.length; i ++) {
            for (int j = bagSize; j >= weight[i]; j --) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }

        //打印dp数组
        for (int j = 0; j <= bagSize; j++){
            System.out.print(dp[j] + " ");
        }

    }

}
